package com.demo93_复原ip地址;

import java.util.ArrayList;
import java.util.List;

public class Solution {
    public static void main(String[] args) {
        List<String> list = restoreIpAddresses("101023");
        for (String s : list) {
            System.out.println(s);
        }
    }
    public static List<String> restoreIpAddresses(String s) {
        List<String> list = new ArrayList<>();
        if(s.length()<4||s.length()>12){
            return list;
        }

        dfs(s,1,0,list,new StringBuilder());

        return list;
    }

    public static void dfs(String s,int part,int startIndex,List<String> list,StringBuilder stringBuilder){
        // 边界条件: 如果到了第5部分
        if (part==5&&startIndex==s.length()){
            // 删除掉上一次添加的逗号
            stringBuilder.deleteCharAt(stringBuilder.length() - 1);
            String result = stringBuilder.toString();
            list.add(result);
            stringBuilder.append(".");
            return;
        }
        if (part==5&&startIndex!=s.length()){
            return;
        }

        // 横向遍历 第 part 部分

        for (int i = startIndex; i <3+startIndex&&(i<s.length()); i++) {
            // 如果当前为0,这部分只能为0
            if (s.charAt(startIndex)=='0'){
                stringBuilder.append(0).append(".");
                // 纵向递归
                dfs(s,part+1,i+1,list,stringBuilder);
                // 回溯: 删除掉这个逗号, 以及本次的添加元素
                for (int k = 0; k < 2; k++) {
                    stringBuilder.deleteCharAt(stringBuilder.length()-1);
                }
                return;
            }
            // 剩余部分的长度 如果小于这个 每部分取 1 位的长度  或者 大于每部分取3位数字 , 那么也是不符合的
            if (s.length()-startIndex<(5-part)||s.length()-startIndex>(5-part)*3){
                return;
            }
            //Integer value = Integer.valueOf(s.substring(startIndex, i + 1));
            // 只有当这个每一部分取到第3位时才需要判断这个是否是大于255
            if (i==(2+startIndex)&&Integer.parseInt(s.substring(startIndex,i+1))>255){
                return;
            }

            // 处理本次遍历的结果
            stringBuilder.append(s, startIndex, i+1).append(".");
            // 纵向递归 下一个部分
            dfs(s,part+1,i+1,list,stringBuilder);
            // 回溯: 删掉逗号 以及 添加的字符数 i+2
            for (int j = 0; j < i-startIndex+2; j++) {
                stringBuilder.deleteCharAt(stringBuilder.length()-1);
            }
        }

    }
}
